package question.solution208;

import question.SolutionTemplate;

import java.util.HashMap;
import java.util.Map;

public class Solution208 implements SolutionTemplate {

    class Trie {

        // 当charactor为0时，为根节点
        char charactor;
        // false 说明当前字符路径不存在，单词不存在
        boolean exist;
        // 存储下一个字符及其对应节点
        Map<Character, Trie> nextCharactorMap = new HashMap<>();

        /** Initialize your data structure here. */
        public Trie() {
            charactor = '0';
            exist = false;
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            Map<Character, Trie> characterMap = nextCharactorMap;
            boolean nodeExist = true;
            int i;
            Trie nextCharactorNode = null;
            for(i=0;i<word.length();i++){
                nextCharactorNode = characterMap.get(word.charAt(i));
                if(null == nextCharactorNode){
                    nodeExist = false;
                    break;
                }
                characterMap = nextCharactorNode.nextCharactorMap;
            }
            if(nodeExist){
                if(null != nextCharactorNode){
                    nextCharactorNode.exist = true;
                }
                return;
            }
            for(int j=i;j<word.length()-1;j++){
                Trie pathNode = createPathNode(word.charAt(j));
                characterMap.put(word.charAt(j), pathNode);
                characterMap = pathNode.nextCharactorMap;
            }
            Trie pathEndNode = createPathEndNode(word.charAt(word.length()-1));
            characterMap.put(word.charAt(word.length()-1), pathEndNode);
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            Map<Character, Trie> characterMap = nextCharactorMap;
            boolean pathExist = true;
            Trie node = null;
            for(int i=0;i<word.length();i++){
                node = characterMap.get(word.charAt(i));
                if(null == node){
                    break;
                }
                characterMap = node.nextCharactorMap;
            }
            if(null != node && node.exist){
                return true;
            }
            return false;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            Map<Character, Trie> characterMap = nextCharactorMap;
            Trie node = null;
            for(int i=0;i<prefix.length();i++){
                node = characterMap.get(prefix.charAt(i));
                if(null == node){
                    break;
                }
                characterMap = node.nextCharactorMap;
            }
            if(null != node){
                return true;
            }
            return false;
        }

        private Trie createPathNode(char val){
            Trie node = new Trie();
            node.charactor = val;
            node.exist = false;
            return node;
        }

        private Trie createPathEndNode(char val){
            Trie node = new Trie();
            node.charactor = val;
            node.exist = true;
            return node;
        }
    }


    public void test() {
        Trie trie = new Trie();
        trie.insert("apple");
        boolean r1 = trie.search("apple");   // 返回 True
        boolean r2 = trie.search("app");     // 返回 False
        boolean r3 = trie.startsWith("app"); // 返回 True
        trie.insert("app");
        boolean r4 = trie.search("app");     // 返回 True

        return;
    }
}
